package class02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * todo:
 * 有错误
 */
public class Code02_1_reversePairs {

	public static int reversePairs(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		return mergeSort(arr, 0, arr.length - 1);
	}

	// arr[L...R] 既要排好序，也要记录逆序对的数量
	public static int mergeSort(int[] arr, int l, int r) {
		if (l == r) {
			return 0;
		}
		int mid = l + ((r - l) >> 1);
		return mergeSort(arr, l, mid) //左侧排序记录逆序对的数量
				+ mergeSort(arr, mid + 1, r) //右侧排序记录逆序对的数量
				+ merge(arr, l, mid, r);  //合并时记录逆序对的数量
	}

	public static int merge(int[] arr, int l, int m, int r) {
		int[] help = new int[r - l + 1];
		int i = 0;
		int p1 = l;
		int p2 = m + 1;
		int res = 0;
		List list = new ArrayList();
		while (p1 <= m && p2 <= r) {

			//方法一：从大到小的排序问题的变式 => 右边有几个数比a小

			res += arr[p1] > arr[p2] ? (r - p2 + 1) : 0;
/*			if (arr[p1] > arr[p2]) {
				int[] pair = new int[2];
				pair[0] = arr[p1];
				pair[1] = arr[p2];

				System.out.println(pair[0]+","+pair[1]);
			}*/
			help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];


/*			//方法二：由小到大排序，看左边有多少比右边大的

			res += arr[p1] > arr[p2] ? (m - p1 + 1) : 0; //merge过程中产生小和
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];


	*//*		if(arr[p1] <= arr[p2]){
				help[i++] = arr[p1++];
			}else if(arr[p1] == arr[p2]){
				help[i++] = arr[p2++];
			}else{
				res += m - p1 + 1;
				help[i++] = arr[p2++];
			}*//*

			System.out.println(Arrays.toString(arr));*/
		}

		while (p1 <= m) {
			help[i++] = arr[p1++];
		}
		while (p2 <= r) {
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {
			arr[l + i] = help[i];
		}

		return res;
	}





	// for test
	public static void main(String[] args) {

		int[] arr = new int[]{5,4,3,2,1};
		System.out.println(reversePairs(arr));
	}



}
